Switching elements have the ability to receive data from multiple sources and to transmit such data to multiple destinations. Each source communicates to a switching element through an ingress interface (also called ingress port on the switching element). A switching element transmits data to each destination by driving its egress interface (also called egress port).
FIG. 1 illustrates a switching element having 4 ingress ports and 4 egress ports. Certain types of switching elements are referred to as fully-connected switches while others are referred to as partially-connected switches. A fully-connected switch, such as illustrated in FIG. 1, can direct data from any ingress port to any egress port. A full-connected switch with equal number of ingress and egress ports, where N is the number of ingress ports, will have N2 possible paths from ingress port to egress port.
Each path or connection from ingress port to egress port can be referred to as a “port pair”. For example: a switching element with 4 ingress and 4 egress ports will have a total of 16 possible port pairs. FIG. 1 also illustrates the port pair connections of a fully connected switching element having 4 ingress ports and 4 egress ports.
Typically, a data source connected to a single ingress port can generate multiple unique streams of data. Each stream of data can be tagged with a channel number by the source. A channelized switching element can direct individual channels on an ingress port to a particular channel of an egress port. This is similar to sending data with a source address and a destination address.
FIG. 2 illustrates a switching element with active channels driving ingress ports, queue elements that store data in transit to an egress channel of an egress port. Most switching elements are required to store received data until the data is transmitted to the egress ports. The received data is typically stored in queues within the switching element, as shown in FIG. 2. Because the data is channelized, each channel of data requires a queue. For example: a switching element with 4 ingress, 4 egress ports, and each ingress and egress port supports 128 channels. The switching element will contain 16*128 individual queues (one queue per channel, per port pair).
Within a switching element, each queue can be referred to as a queue element. Each of the queue elements requires a predetermined amount of storage, or memory, for holding the channel data while in transit from ingress to egress port. The amount of storage a queue element requires is dependent on the characteristics of the data stream. Therefore, not all queue elements require the same amount of storage. Many methods of allocating storage to queue elements are known. One method includes providing dedicated storage for each queue element, while other methods share storage across all the queue elements. For shared storage methods, storage is allocated and de-allocated dynamically as needed. Some methods of dynamic storage allocation allocate memory when a channel is activated (also called provisioning a channel), and de-allocate memory when a channel is de-activated (also called de-provisioning a channel). More complex methods of dynamic storage allocation allocate memory when data arrives at a particular queue and then de-allocate storage as the data exits the queue and is transmitted to the egress port.
Regardless of the method for allocating storage to queue elements, each port pair with one or more active channels must be allocated at least one physical memory element. A port pair with a newly activated channel, and no channel currently active on the port pair, needs a completely empty and dedicated physical memory element, such as a random access memory (RAM) in order to be allocated. In general: a) memory elements cannot be shared between port pairs, as individual memory elements, also called pages, are allocated to individual port pairs; and b) a block of memory cannot be shared between queues, as individual blocks are allocated to individual queues.
For example: a switching element with 16 active port pairs must therefore include a minimum of 16 physical memory elements. An active port pair is defined as a port pair with one or more active channels. The storage available within a memory element is shared either dynamically or statically amongst the queue elements of the port pair. In some examples a switching element with 16 port pairs may have only 1 active channel on a single port pair; depending on the traffic profile of that channel the queue element servicing the channel could require multiple memory elements.
The smallest amount of storage that can be allocated to a queue is typically called a block of memory, or simply a block. Within a memory element, there are multiple blocks of memory available for allocation to queue elements. A single memory element, such as a RAM, is referred to as a page of memory. In this context, the total amount of memory available for all queue elements is equal to the number of pages and these pages are made of blocks.
FIG. 3 illustrates a switch element with 16 memory elements, each port pair having 1 memory element allocated thereto. In this example, every port pair could support an active channel. In the example of FIG. 3, the maximum number of channels that could be supported for each port pair is equal to the number of blocks within each individual memory element.
FIG. 4 illustrates a switch element with 16 memory elements in which a single port pair is allocated all available memory elements. In this example, only port pair 3-3 (ingress-egress port) could support an active channel. In the example of FIG. 4, the maximum number of channels that could be supported for port pair 3-3 is equal to the total number of blocks within all memory elements.
In switching elements with dynamic memory allocation, when no channels are active, every block of memory is unallocated and therefore every page of memory is also unallocated. As the first channel is activated, the switching element, which could be hardware or software controlled, allocates a memory element to the port pair and also allocates a block within that memory element to the queue element servicing the channel.
One method to track allocated blocks is via a block allocation table. The block allocation table tracks the allocated blocks, the memory element allocation to a port pair, the association of a block to a queue element and the logical order of the block within the queue element. The block allocation table can be maintained by software or hardware. When additional channels are activated and the additional channels are associated with different port pairs, the switching element must allocate new memory elements to port pairs.
Channels activated on an already active port pair can be allocated blocks of memory from an already allocated memory element. When no blocks are available within the already allocated memory element, because they are taken by other queue elements, the switching element must allocate a new memory element to the port pair. As channels are de-activated, the switching element must de-allocate the blocks of memory. Once all blocks of a memory element have been de-allocated, the switching element can de-allocate the memory element itself, making it available to other port pairs.
This repeated process of channel activation and de-activation can cause the range of available memory to become sparsely allocated, or partially allocated. When the available memory becomes sparsely allocated, allocated blocks of memory are non-contiguous, which can leave a port pair with more than 1 memory element allocated but with only a few blocks allocated in each memory element. Some switching elements also support re-sizing of queues as the data stream characteristics change. The re-sizing of queues, combined with channel activation and de-activation, can also result in the available memory becoming sparsely allocated, or fragmented. After a memory element is allocated to a port pair, a block of memory in the memory element is further allocated to a channel on the port pair, or to a queue servicing the channel.
Known memory defragmentation approaches typically focus on remapping blocks of memory such that all used/allocated blocks are grouped together. However, such known approaches do not take into consideration the association of memory elements with port pairs.
Improvements in memory reallocation in the context of port pairs are therefore desirable.